package basic.study.leetcode;

/**
 * @ClassName Hard10
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/17 11:04
 * @Version 1.0
 */
public class Hard10 {
    class SOlution {
        /**
         * 回溯法
         * @param text
         * @param pattern
         * @return
         */
        public boolean isMatch0(String text, String pattern) {
            if (pattern.isEmpty()) {
                return text.isEmpty();
            }
            boolean firstMatch = (!text.isEmpty() && (pattern.charAt(0)== text.charAt(0) || pattern.charAt(0) == '.'));

            if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
                //匹配0个
                return isMatch0(text, pattern.substring(2)) || (firstMatch && isMatch0(text.substring(1), pattern));
            } else {
                return firstMatch && isMatch0(text.substring(1), pattern);
            }
        }

        /**
         * 动态规划，自顶向下
         * @param text
         * @param pattern
         * @return
         */
        Result[][] memo;
        public boolean isMatch1(String text, String pattern) {
            memo = new Result[text.length()+1][pattern.length()+1];
            return dp(0, 0, text, pattern);
        }

        private boolean dp(int i, int j, String text, String pattern) {
            if (memo[i][j] != null) {
                return memo[i][j] == Result.TRUE;
            }
            boolean ans;
            if (j == pattern.length()) {
                ans =  i == text.length();
            } else {
                boolean first_match = (i < text.length() &&
                                        pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.');

                if (j+1 <pattern.length() && pattern.charAt(j+1) == '*') {
                    ans = (dp(i, j+2, text, pattern) || first_match && dp(i+1, j, text, pattern));
                } else {
                    ans = first_match && dp(i+1, j+1, text, pattern);
                }
            }
            memo[i][j] = ans?Result.TRUE:Result.FALSE;
            return ans;
        }


        /**
         * 动态规划，自底向上
         * @param text
         * @param pattern
         * @return
         */
        public boolean isMatch2(String text, String pattern) {
            boolean[][] dp = new boolean[text.length()+1][pattern.length()+1];
            dp[text.length()][pattern.length()] = true;

            for (int i = text.length(); i >= 0; i--) {
                for (int j = pattern.length(); j >= 0; j--) {
                    boolean firstMatch = (i < text.length() &&
                                        pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.');
                    if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*') {
                        dp[i][j] = dp[i][j+2] || firstMatch && dp[i+1][j];
                    } else {
                        dp[i][j] = firstMatch && dp[i+1][j+1];
                    }
                }
            }
            return dp[0][0];
        }

    }

    enum Result {
        TRUE, FALSE;
    }
}
